1. 1. Field of the Invention
The present invention relates to a method for automatically determining wiring routes among terminals which are arranged on an integrated circuit, and in particular to a method for automatically determining wiring routes for designing a wiring pattern of a semiconductor integrated circuit.
2. 2. Description of Background Art
Recently, to automatically design a wiring pattern of a semiconductor integrated circuit, layout CAD programs which are operated by utilizing a general-purpose computer have been developed.
The automatic design is made up of two procedures. A first procedure is a global routing procedure for roughly determining wiring routes. The global rough wiring route is called a global route. A second procedure is a detail routing procedure for precisely determining a final routing pattern according to the global routes determined by the first procedure. The final routing pattern determined by the detail routing procedure is called a detail route.
In the global routing procedure, initially, a routing area is divided into global routing cells of which the side length is larger than the interval of the actual wires. Therefore, the maximum number of detail routes which can pass through a global routing cell in parallel is determined by the side length of the cell. The maximum number is called wiring capacity. The global route is determined without exceeding the wiring capacity in the global routing procedure.
In the detail routing procedure, the final routing pattern is determined according to the global routes.
The first procedure and the second procedure for respectively determining the global route and the detail route are described as an example with reference to FIG. 1 as follows.
As shown in FIGS. 1(a) to 1(d), a pair of numbered terminals, which are set to the same electric potential, are connected to determine the wiring routes in a routing area 210. To roughly determine the wiring route among the terminals, two typical wiring methods are known.
One is a maze method (C.Y. Lee, "An Algorithm for Path Connections and Its Applications", IRE Trans. Electron. Comput., Vol. EC-10, pp. 346-365, 1961). The other is a segment search method ( K. Mokami etc., "A Computer Program for Optimal Routing of Printed Circuit Connections", IFIPS Proc., pp. 1475-1478, 1968).
In the conventional automatic wiring methods such as the maze method or the segment search method, wiring routes 211 between like-numbered terminals are determined serially as shown in FIGS. 1(a) to 1(d). However, the above automatic wiring method increases the processing time and enlarges the circuit.
In recent semiconductor integrated circuits, many drawbacks have occurred as the complexity of integrated circuits advances. That is, the processing time required for the layout of the wiring route is rapidly increased. For example, when the number of parts integrated in the semiconductor is M, the processing time is proportional to M.sup.2. In short, the increase in processing time required for the layout is greater than the improvement in executing speed in the general-purpose computer.
To solve those drawbacks, recently, an automatic wiring route determination method for executing a wiring process by utilizing a plurality of processors in parallel has been proposed (H. Nelson Brady, "MIMD Organization for the Execution of Interconnection Routing Algorithm", IEEE Circuits and Device Magazine, pp. 39-43, 1985, first published in Japanese Patent Publications No. s62-115574, and s62-186351).
One example of the above method is described as follows with reference to FIG. 2.
As shown in FIG. 2, a palr of terminals with like numbers are connected to determine wiring routes. In this parallel wiring method, initially, a routing area 210 is divided into a plurality of small areas 220, 221, 222, 223 (four in this example) as shown in FIG. 2(b). And then, wiring routes between a pair of like-numbered terminals and is included in the same small area are determined as shown in FIG. 2(c). In this example, the routes between terminals 1, 1, terminals 2, 2, ---, and terminals 6, 6 are respectively determined. When all the wiring routes have been determined, the processing is stopped. On the other hand, when no wired terminals exist, some small areas are combined to compose a larger new small area. In FIG. 2(c), because no wired terminals 7, 8, 9, and 10 exist, the small areas 220 to 223 are combined to compose a new small area 225 (in thls example, the area 225 is the same as the routing area 210). And then, the wiring routes between the terminals included in the area 225 are determined. Moreover, when no wired terminals still exist, the combination of the small areas is repeated to determine the all wiring routes.
For example, when the routing area 210 is divided into N small areas to process by using N processors, the all N processors can be operated in a first step. That is, the processing is executed in parallel N times. Thereafter, some small areas are combined to compose a new small area before determining the wiring routes of non-wired terminals in the new small area in a second step. To simplify the wiring procedures, four (2.times.2) small areas in close proximity are combined to compose a new small area. That is, the routing area 210 is divided into N/4 small areas. Therefore, N/4 processors can be operated to determine the wiring routes in the second step. That is, the other processors are not needed. In the same manner, N/16 processors can be operated to determine the wiring routes in a third step. That is. the other (N-N/16) processors are not needed.
Accordingly, in the parallel wiring method as described in the above example, the small areas including no wired terminals are combined to compose a new small area. Therefore, the number of the divided small areas is decreased while the wiring process proceeds. That is, the number of processors operated in parallel is decreased so that the number of unused processors increases.
On the other hand, a distribution graph of a wiring number is shown in FIG. 3. The distribution is determined according to the layout of a typlcal real circuit.
As shown in FIG. 3, the abscissa corresponds to a group of cut lines 130. The cut lines 230 are positioned in the routing area 210 as shown in FIG. 4. The ordinate indicates the number of wires across a corresponding cut line 130. Judging from the distribution. the number of wires being across each cut line 130 is almost equal over the entire routing area 210.
Accordingly, in the parallel wiring method described in the above example, because the wire is necessarily across the boundary line between the small areas, the small areas in the first step must be combined step by step to finally compose the largest small area which is identical to the routing area 210 to complete the wiring process.
As mentioned above, in the conventional automatic wiring method, the wiring process of a large scale circuit can not be completed in a practical process time. Also, it is inefficient to use the above method in the parallel wiring method to solve the above drawback.
As mentioned above, in the conventional automatic wiring method, the small areas are processed one by one by using one general-purpose computer. Therefore, the layout of a large scale integrated semiconductor is impossible to be executed in a practical processing time, even using the highest speed computer now in existence.